#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/22 9:13
# ===========================================
#       题目名称： 22. 括号生成
#       题目地址： https://leetcode.cn/problems/generate-parentheses/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            枚举出来 然后取出有效的
    """

    def generateParenthesis(self, n):
        res = []
        cur_n = 0  # 当前n
        while cur_n < 2 * n:
            if res:
                temp_res = []
                for cur_res in res:
                    temp_res.append(cur_res + "(")
                    temp_res.append(cur_res + ")")
                res = temp_res
            else:
                res.append("(")
                # res.append(")")
            cur_n += 1
        # 取出那些有效的括号
        cur_index = 0
        while cur_index < len(res):
            cur_parentheses = res[cur_index]
            while cur_parentheses:
                change_before_len = len(cur_parentheses)
                cur_parentheses = cur_parentheses.replace("()", "")
                change_after_len = len(cur_parentheses)
                if change_after_len == change_before_len:
                    break
            if cur_parentheses:
                del res[cur_index]
            else:
                cur_index += 1
        return res

if __name__ == '__main__':
    s = Solution()
    # ["((()))","(()())","(())()","()(())","()()()"]
    print(s.generateParenthesis(n=3))
    # ["()"]
    print(s.generateParenthesis(n=1))
